package com.wu.leetcode.leetcode105;

/**
 * Leetcode105-从前序与中序遍历序列构造二叉树
 */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0 || inorder == null || inorder.length == 0) {
            return null;
        }
        return build(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }

    private TreeNode build(int[] preorder, int[] inorder, int preL, int preR, int inL, int inR) {
        if (preL > preR || inL > inR) {
            return null;
        }
        TreeNode node = new TreeNode(preorder[preL]);
        int i = 0;
        while (i <= inR && inorder[i] != preorder[preL]) {
            i++;
        }
        node.left = build(preorder, inorder, preL + 1, i + preL - inL, inL, i - 1);
        node.right = build(preorder, inorder, preR + i + 1 - inR, preR, i + 1, inR);
        return node;
    }
}
